1. Field of the Invention
The present invention relates generally to computer graphics.
2. Related Art
Computer graphics systems render all kinds of objects for screen display and animation. An object is modeled in object space by a set of primitives (also called graphics primitives). Examples of primitives include, but are not limited to, triangles, polygons, lines, tetrahedra, curved surface, and bit-map images. Each primitive includes one or more vertices that define the primitive in terms of position, color, depth, texture, and/or other information helpful for rendering. Each primitive can be further broken up into fragments. Each fragment when projected for rendering on a screen, corresponds to all or part of an area of one pixel. For example, a polygon or curved surface can be broken up through scan conversion into fragments. Fragments can also include vertices or per-vertex information.
Textures are used to add further visual information. By utilizing texture mapping techniques, color and other details can be applied to areas and surfaces of objects. In texture mapping, a pattern image (also referred to as a xe2x80x9ctexturexe2x80x9d or texture mapxe2x80x9d) is combined with an area or surface of an object to produce a modified object with the added texture detail. For example, given the outline of a featureless cube and a texture map defining a wood grain pattern, texture mapping techniques can be used to xe2x80x9cmapxe2x80x9d the wood grain pattern onto the cube. The resulting display is that of a cube that appears to be made of wood. In another example, terrain (e.g., images of a town, river, vegetation and trees) can be added by texture mapping to an otherwise barren terrain model.
The demand for large textures is increasing. Many graphics applications increasingly demand a large contiguous texture. The cost of increasing texture memory and/or hardware to accommodate a large contiguous texture can be prohibitive.
Due to the importance of large contiguously textured databases to many graphics applications, schemes have been implemented which allow an application to apply massive textures over databases such as terrain, while operating within the limited constraints of hardware resources. These have ranged from software-only schemes which slice the underlying geometry into tiles corresponding to texture files, to hardware implementations which treat the image as a homogeneous entity.
Consider two examples of such schemes, clip-mapping and texture tiling. Clip-mapping is a relatively specialized and sophisticated scheme that uses a clip-map. See, U.S. Pat. No. 5,780,783 issued to Migdal et al. and incorporated in its entirety herein by reference. For example, a clip-map can be a multiresolutional texture map pyramid (such as, a MIP map) clipped to a xe2x80x9cclip sizexe2x80x9d that covers a single view being rendered. See, the example clip-map MW pyramid 100 in FIG. 1A. The image space is treated as a homogeneous entity for texturing purposes. Paging supplies a region 102 of high resolution in the area of most immediate interest with decreasing resolution as one moves away from the region of interest. Naturally the region of interest may be moved with the viewer in order to sustain high resolution in an animated scene. Torroidally wrapped texture addressing can be used to accommodate texture updates in clip-mapping. See, e.g., Tanner et al., xe2x80x9cThe Clipmap: A Virtual Mipmap,xe2x80x9d Computer Graphics Proceedings, Annual Conf. Series, 1998 (SIGGRAPH ""98), pp. 151158. As depicted in FIG. 1B, such torrodial wrapped texture addressing allows new data 102B to be added to a clip-map tile as old data 102A is removed. This is a relatively complex scheme which can be difficult to adopt in many applications which drive consumer-level products.
Texture tiling creates a series of tiles. The tiles represent portions of a contiguous image space. These tiles are applied as unique textures with associated unique texture identifiers (referred to herein as xe2x80x9ctexture IDsxe2x80x9d or xe2x80x9ctexture handlesxe2x80x9d) to a series of tiled geometry segments. This requires that the application or database creator chop the geometric database into tiles to match the texture representation. A database is triangulated when it is chopped up to meet image paging requirements. FIG. 1C shows how an example triangle primitive 110 might have to be divided into four parts when it overlays four texture image tiles (Tile 1, Tile 2, Tile 3, and Tile 4).
Furthermore, as the database is viewed from a distance, ideally one would like fewer tiles to be applied to the database requiring that a quad tree or similar tiling structure be implemented to manage geometric complexity; this in turn requires a quad tree texture representation. While not entirely forced by the geometric issues, a software implementation quickly becomes a rather unwieldy proposition and suffers from some flaws. If implemented without consideration of filtering at the borders of the texture boundaries, there will be apparent texture filtering discontinuities across tile boundaries. The magnitude of these boundaries varies with the level of MIP map being applied to the respective tiles.
Graphics hardware has been built which avoids the need to subdivide the geometry using fragment selection within the range of the texture and multipass rendering on the underlying geometry. With this approach, any fragment outside the immediate texture image is not rasterized. This test is performed repeatedly with different images in different locations in a sequence of rendering passes. The issue of filtering then remains.
One or more extensions have been implemented to cope with filtering while subdividing the geometry in the application. For instance, texture border image support has been designed into graphics hardware implementations to allow filtering under these circumstances to be handled smoothly. Using such a scheme as described in U.S. Pat. No. 5,230,039, which is incorporated herein by reference in its entirety, a portion of the adjacent tile is specified by the application for filtering purposes. This scheme still requires the subdivision of the database based on texture border tiles, but it avoids the filtering artifacts at the tile edges. FIG. 1D shows an example that illustrates the specification of borders to avoid filtering issues. As illustrated, a triangle 120 is divided into fragments 120A and 120B. Fragment 120A will be textured with tile 1 while fragment 120B will be textured with tile 2. Note border portion 122 of fragment 120A and border portion 124 of fragment 120B. These border portions 122,124 will be textured with border portions 126,128 of texture tiles 1 and 2. This scheme provides filtering for a smooth transition between the texture tiles. However, the drawback of having to break the geometry into tiles remains.
A modified scheme described in U.S. Pat. No. 5,815,157, which is incorporated herein by reference in its entirety, uses an adjacent portion of texture memory to store borders of the image tile under consideration to the side of a tile in an oversized region of texture memory. A variation on the scheme is to use a larger portion of texture memory and a texture matrix to manipulate the application of texture coordinates such that the tile of texture under consideration and its borders become part of a contiguous texture memory space. FIG. 1E illustrates an example of an adjusted layout in memory for contiguous mapping. Note texture tile 130 and borders 132 which are stored in a larger portion 134 of texture memory.
To eliminate the strict requirement for geometry subdivision along tile boundaries, a scheme can be implemented where overlapping textures are applied to the image in texture memory. Instead of clamping to the original image boundary, the adjacent images may be addressed for triangles which extend a short way beyond the conventional image border. If one rearranges the in memory representation described in U.S. Pat. No. 5,815,157, it can be seen that conventional hardware may be used and the subdivision of database triangles is avoided. By placing the original texture tile in the center of an oversized texture, it is easy to see that the border images are simply extensions of the original tile in a conventional texture memory addressing scheme.
Another way of visualizing this type of scheme is to see that the texture tiles in memory are actually overlapping with each other. The reason this is done is to avoid geometry which must be textured with two or more separate textures. A remaining constraint on the geometry is that primitives near the edge of a tile may not exceed the size of the region of overlap. FIG. 1F illustrates an example of overlapping texture borders which can be used to supply a single texture to graphics primitives without subdivision. For example, FIG. 1F illustrates texture tiles 1 and 2 which share a common overlap region 140. As a result of overlap region 140, triangle T1 can be textured using only texture tile 1. Similarly, triangle T3 can be textured using only texture tile 2. Triangle T2 can be textured using either of texture tiles 1 or 2 since it lies entirely in overlap region 140. The price of this scheme is increased texture memory usage and redundant texture paging to supply the data for the region of overlap. It also requires non-trivial management of texture memory, since the data on disk is likely to be in a tiled format without the overlap, subloading of texture. Images with memory strides is required, which further reduces paging performance.
What is desired is the ability to decouple geometry from texture tiling and to avoid the need to implement difficult or complex torroidal mapping schemes or tricky underused border schemes. It is also desirable to avoid the redundancy of overlapping texture schemes while increasing the ease of implementation and performance of a paging approach. A system and method is needed which can apply unique texture over extended areas with limited hardware texture memory (requiring paging) while imposing few restrictions upon a database. Extensive hardware, onerous restrictions upon a database, and/or difficult implementations which waste paging bandwidth need to be reduced or avoided.
The present invention solves the above problems and needs. In one embodiment, a novel graphics extension is provided that allows an application to seamlessly apply large contiguous texture over a database while supporting the paging of texture and operating within the constraints of limited available texture memory and real-time rendering requirements.
In one embodiment, the present invention provides a solution that allows the specification of a texture image as the border to another for texture tiling purposes. This means that when texture addressing extends beyond the region within a texture map another image is addressed instead of a repeated version of the original image or a border color or a reflected version of the image as is currently common practice. This specification of a border image would include the ability to specify different texture images for each of the 8 tiling directions: +s, xe2x88x92s, +t, xe2x88x92t, +s+t, xe2x88x92sxe2x88x92t, xe2x88x92s+t, and +sxe2x88x92t. Using this system, an array of images could be linked to one other to form a massive meta image. Within the region covered by these images, a graphics primitive such as a triangle or triangle strip which is less than the size of 3 individual images could be textured with a single unique texture tile. Tiles could optionally be paged and even joined at different resolutions. In addition more parameters could be optionally supported to allow the mapping of different sized images to be adjacent to one another (to allow different sized tiles at different resolutions over various parts of a database).
In one embodiment, a routine for texture processing uses texture tiling and adjacency information. A base texture image and adjacent border textures are loaded in texture memory. The base texture image is associated with adjacency information. A graphics primitive is then mapped to adjacent border textures identified by the adjacency information. In one example, this mapping includes evaluating texture coordinate values to determine when texture coordinates are outside a range of a base texture image being texture mapped, and determining which adjacent border texture corresponds to the texture coordinates evaluated to be outside the base image. This determination is made using adjacency information which identifies the direction of the adjacent border texture relative to the base image.
The present invention can be used by a broad base of developers and is applicable to many general rendering tasks. The implementation of the present invention can be straightforward. The size of primitives at the borders can be increased. The size of graphics primitives is not constrained by the size/redundancy of an overlap region. This improves the ease of use, reduces the database constraints and potentially increases the adoption of a system and method according to the present invention by software developers.
The present invention provides a more generally applicable extension than clip-mapping alone. This extension has broad use in graphics applications while being easy to implement and straighforward to program.
Further, geospecific texture mapping is a key requirement for many applications. The present invention makes database and software support for geospecific paging easier, it also makes it more likely to be adopted by independent hardware vendors (IHVs) given the generally useful nature of the idea.
By providing a texture object with border textures for tiling purposes, the present invention can elegantly extend the capability of existing hardware to support unrestricted texture roaming with little or no texture memory redundancy and few restrictions on database construction. It avoids the traditional problem of having to chop up the database into tiles and does not require that overlapping images in memory be created.
The present invention can be used in any graphics application, toolkit, library, software, hardware or other graphics system.
Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with reference to the accompanying drawings.